package branchandbound;

import java.util.*;

public class HaFuMan {
    public static void main(String[] args) {

        List<Node> nodes = new ArrayList<>();
        //记录输入name顺序
        List<String> nameList = new ArrayList<>();
        Scanner input = new Scanner(System.in);
        String name[] = input.nextLine().split(" ");
        int w[] = new int[name.length];
        String[] splitWeight = input.nextLine().split(" ");
        for (int i = 0; i < splitWeight.length; i++) {
            w[i] = Integer.parseInt(splitWeight[i]);
            nodes.add(new Node(name[i], w[i]));
            nameList.add(name[i]);
        }

        Node node = CreateTree(nodes);
        Map<String, String> map = new HashMap<>();
        getHuffManCode(map, node, "");
        for (String namel : nameList) {
            System.out.println(namel + ":" + map.get(namel));
        }

    }

    /**
     * 获取哈夫曼code
     *
     * @param map
     * @param rootNode
     * @param huffManCode
     */
    public static void getHuffManCode(Map<String, String> map, Node rootNode, String huffManCode) {

        if (rootNode.getName() != null) {
            map.put(rootNode.getName(), huffManCode);
            return;
        }
        getHuffManCode(map, rootNode.getLchild(), huffManCode + "0");
        getHuffManCode(map, rootNode.getRchild(), huffManCode + "1");
        return;
    }

    /**
     * 创建哈弗曼树
     */
    private static Node CreateTree(List<Node> nodes) {

        while (nodes.size() > 1) {

            //1. 排序Node的weight，但由于list或Collections自带的Sort在weight相同时无法按
            // name进行排序 故自定义排序
            //nodes.sort(Comparator.comparingInt(Node::getWeight));
            for (int i = nodes.size() - 1; i > 0; i--) {
                for (int j = 0; j <= i - 1; j++) {
                    if (nodes.get(j).getWeight() <= nodes.get(j + 1).getWeight()) {
                        Node temp = nodes.get(j);
                        nodes.set(j, nodes.get(j + 1));
                        nodes.set(j + 1, temp);
                    }
                }
            }
            // 构建左节点
            Node left = nodes.get(nodes.size() - 1);
            // 构建右结点
            Node right = nodes.get(nodes.size() - 2);
            // 得出前面两个结点的父亲结点
            Node parent = new Node(null, left.getWeight() + right.getWeight());
            parent.setLchild(left);
            parent.setRchild(right);
            // 删除List集合中的用过的两个结点
            nodes.remove(left);
            nodes.remove(right);
            // 将生成的父亲结点放入到List集合中去
            nodes.add(parent);
        }
        return nodes.get(0);
    }
}

class Node {

    private String name;
    private int weight;
    private Node lchild;
    private Node rchild;


    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public int getWeight() {
        return weight;
    }

    public void setWeight(int weight) {
        this.weight = weight;
    }

    public Node getLchild() {
        return lchild;
    }

    public void setLchild(Node lchild) {
        this.lchild = lchild;
    }

    public Node getRchild() {
        return rchild;
    }

    public void setRchild(Node rchild) {
        this.rchild = rchild;
    }


    public Node(String name, int weight) {
        this.name = name;
        this.weight = weight;
    }
}

